package leetcode

import kotlinetc.println

//https://leetcode.com/problems/maximum-product-subarray/
/**
Given an integer sort.getArray nums, find the contiguous subarray within an sort.getArray (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
和[maxSubArray]类似
 */

fun main(args: Array<String>) {

    maxProduct(intArrayOf(-2, 0, -1)).println()
}

/**
 * 找出连续的最大乘积乘积：这题看似和[maxSubArray]类似，实则复杂了许多，由于0和负数的存在，
 * 可能当前的最大数直接变成最小负数，或者归零，最小数可能变成最大数，所以在记录当前最大数时，同时保留最小数，
 * 因为 最大数 只可能在 当前数 、当前数和最大数乘积  和 当前数与最小数乘积  这三个结果之中产生，
 * 然后更新最大数 和最小数
 *
 * 思路来自//https://leetcode.com/problems/maximum-product-subarray/discuss/292529/Java-intuitive-solution
 */
//Classic
fun maxProduct(nums: IntArray): Int {

    var result = nums[0]
    var min = nums[0]
    var max = nums[0]

    val size = nums.size
    for (i in 1 until size) {
        val it = nums[i]
        val nextMax = Math.max(it, Math.max(max * it, min * it))
        val nextMin = Math.min(it, Math.min(max * it, min * it))
        max = nextMax
        min = nextMin
        result = Math.max(result, max)
    }
    return result
}